package com.company.笔试.topK排序;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author 11
 * @Date 2021/6/7 20:36
 * @Version 1.0
 */
import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();//结果数组
        if (input == null || k <= 0 || k > input.length) {//判空
            return res;
        }
        Queue<Integer> queue = new PriorityQueue<>(k, Collections.reverseOrder());//初始化一个大顶堆  前k个数

        for (int i = 0; i < input.length; i++) {

            if (queue.size() < k) {//如果小于k 就可以放元素进去
                queue.add(input[i]);
            } else {//否则判断新的数是否大于堆顶，如果大于堆顶，然后添加新的数
                if (input[i] < queue.peek()) {

                    queue.remove();
                    queue.add(input[i]);
                }
            }
        }
        //取出堆中的数放进结果列表中
        while (!queue.isEmpty()) {
            res.add(queue.remove());
        }
        return res;
    }
}
